package tree

import (
	"container/list"
	"fmt"
)

/**
 * 二叉树相关函数工具
 * 由于slice基本类型（如[]int）不支持存nil，无法表示非完全二叉树。
 * 这里统一用*list.List，并提供了BuildList函数
 */

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func BuildTree(lst *list.List) *TreeNode {
	if lst.Len() == 0 {
		return nil
	}
	queue := list.New()
	root := &TreeNode{lst.Front().Value.(int), nil, nil}
	queue.PushBack(root)
	//遍历输入的list的值
	for cur := lst.Front().Next(); cur != nil; {
		node := queue.Remove(queue.Front()).(*TreeNode)
		//创建左节点
		if cur.Value != nil {
			node.Left = &TreeNode{cur.Value.(int), nil, nil}
			queue.PushBack(node.Left)
		} else {
			node.Left = nil
		}
		cur = cur.Next()
		//创建右节点
		if cur == nil {
			break
		}
		if cur.Value != nil {
			node.Right = &TreeNode{cur.Value.(int), nil, nil}
			queue.PushBack(node.Right)
		} else {
			node.Right = nil
		}
		cur = cur.Next()
	}

	return root
}

func Tree2list(root *TreeNode) *list.List {
	res := list.New()
	queue := list.New()
	queue.PushBack(root)
	for queue.Len() > 0 {
		//出队一个节点
		node := queue.Remove(queue.Front()).(*TreeNode)
		if node == nil {
			res.PushBack(nil)
		} else {
			res.PushBack(node.Val)
			//非空左右子节点入队
			queue.PushBack(node.Left)
			queue.PushBack(node.Right)
		}
	}
	for res.Len() > 0 && res.Back().Value == nil {
		res.Remove(res.Back())
	}
	return res
}

func BuildList(nums ...interface{}) *list.List {
	lst := list.New()
	for _, num := range nums {
		lst.PushBack(num)
	}
	return lst
}

func PrintList(list *list.List) {
	fmt.Print("[")
	for cur := list.Front(); cur != nil; cur = cur.Next() {
		fmt.Print(cur.Value)
		if cur.Next() != nil {
			fmt.Print(",")
		}
	}
	fmt.Println("]")
}

//前序遍历打印
func PreOrderPrint(root *TreeNode) {
	if root == nil {
		return
	}
	stack := list.New()
	stack.PushBack(root)
	for stack.Len() > 0 {
		node := stack.Remove(stack.Back()).(*TreeNode)
		fmt.Print(node.Val, " ")
		if node.Right != nil {
			stack.PushBack(node.Right)
		}
		if node.Left != nil {
			stack.PushBack(node.Left)
		}
	}
	fmt.Println()
}

//中序遍历
func InOrderPrint(root *TreeNode) {
	stack := list.New()
	node := root
	for stack.Len() > 0 || node != nil {
		for node != nil {
			stack.PushBack(node)
			node = node.Left
		}
		top := stack.Remove(stack.Back()).(*TreeNode)
		fmt.Print(top.Val, " ")
		node = top.Right
	}
	fmt.Println()
}
